package com.tgy.algorithm.base.morris;

import com.tgy.algorithm.base.other.BiTreeNode;

import java.util.Stack;

public class _morris01 {

    public static BiTreeNode general() {

        /**
         * 0,1,3,1,0,5,2,
         *
         *             0
         *         1        2
         *      3     4   5
         *          6
         */
        BiTreeNode root = new BiTreeNode(0);

        root.left = new BiTreeNode(1);
        root.right = new BiTreeNode(2);

        root.left.left = new BiTreeNode(3);
        root.left.right = new BiTreeNode(4);
        root.right.left = new BiTreeNode(5);
        root.left.right.left = new BiTreeNode(6);

        return root;
    }

    public static void morris(BiTreeNode root) {

        BiTreeNode node = root;
        System.out.println(node.value);
        BiTreeNode nextNode;
        while (node != null) {

            nextNode = node.left;
            if (nextNode != null) {
                while (nextNode != null && nextNode.right != null && nextNode.right != node) {
                    nextNode = nextNode.right;
                }

                if (nextNode.right == null) {
                    nextNode.right = node;
                    node = node.left;
                    System.out.print(node.value + ",");
                }else {
                    nextNode.right = null;
                    // 左边遍历完了，直接去右边
                    node = node.right;
                    if (node != null) {
                        System.out.print(node.value + ",");
                    }
                }

            }else {
                // 左边没有节点，去右边
                node = node.right;
                if (node != null) {
                    System.out.print(node.value + ",");
                }
            }
        }

    }

    // morris的前序遍历
    public static void morrisProOrder(BiTreeNode root) {

        BiTreeNode node = root;
        BiTreeNode nextNode;
        while (node != null) {
            nextNode = node.left;
            if (nextNode != null) {
                while (nextNode != null && nextNode.right != null && nextNode.right != node) {
                    nextNode = nextNode.right;
                }

                if (nextNode.right == null) {
                    nextNode.right = node;
                    System.out.print(node.value + ",");
                    node = node.left;
                    continue;
                }else {
                    // 第二次进入
                    nextNode.right = null;
                    // 左边遍历完了，直接去右边
                    node = node.right;
                }
            }else {
                if (node != null) {
                    System.out.print(node.value + ",");
                }
                // 左边没有节点，去右边
                node = node.right;
            }
        }
    }

    public static void morrisInOrder(BiTreeNode root) {

        BiTreeNode node = root;
        BiTreeNode nextNode;
        while (node != null) {
            nextNode = node.left;
            if (nextNode != null) {
                while (nextNode != null && nextNode.right != null && nextNode.right != node) {
                    nextNode = nextNode.right;
                }

                if (nextNode.right == null) {
                    nextNode.right = node;
                    node = node.left;
                }else {
                    // 第二次进入
                    nextNode.right = null;
                    // 左边遍历完了，直接去右边
                    System.out.print(node.value + ",");
                    node = node.right;
                }
            }else {
                if (node != null) {
                    System.out.print(node.value + ",");
                }
                // 左边没有节点，去右边
                node = node.right;
            }
        }
    }


    public static void biTreeInOrder(BiTreeNode root) {

        if (root == null) {
            return;
        }

        Stack<BiTreeNode> stack = new Stack<>();
        BiTreeNode node = root;
        while (!stack.isEmpty() || node != null) {
            if (node != null) {
                // 放入到栈中的只在这里放入，只需要给的好对应到node节点
                stack.push(node);
                node = node.left;
            }else {
                node = stack.pop();
                System.out.println(node.value);
                node = node.right;
            }
        }
    }

    public static void biTreePostOrder(BiTreeNode root) {

        if (null == root) {
            return;
        }

        Stack<BiTreeNode> stack = new Stack<>();
        stack.push(root);

        Stack<Integer> reStack = new Stack<>();

        while (!stack.isEmpty()) {
            BiTreeNode node = stack.pop();
            if (node.left != null) {
                stack.push(node.left);
            }

            if (node.right != null) {
                stack.push(node.right);
            }

            reStack.push(node.value);
        }

        while (!reStack.isEmpty()) {
            Integer pop = reStack.pop();
            System.out.print(pop + ",");
        }
        System.out.println();
    }

    public static void biTreePostOrder01(BiTreeNode root) {

        Stack<BiTreeNode> stack = new Stack<>();
        stack.push(root);
        BiTreeNode preVisited = root;
        BiTreeNode node;
        while (!stack.isEmpty()) {
            node = stack.peek();
            if (node.left != null) {
                stack.push(node.left);
            }else {
                node = stack.peek();
                if (node.left == preVisited) {

                }
            }
        }

    }

    public static void main(String[] args) {
        BiTreeNode root = general();
//        morris(root);
//        morrisProOrder(root);
//        morrisInOrder(root);
        biTreePostOrder(root);
    }
}
